English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Rezerwacje (hot)
Hotel
Memory limit: 64 MB
Your friend owns a hotel at the seaside in Gdynia. The summer season is just starting and he is overwhelmed by the number of offers from potential customers. He asked you for help in preparing a reservation system for the hotel.
There are 
rooms for rent in the hotel, the 
-th room costs your friend
zlotys of upkeep (only if it is rented) and has a capacity of
people.
You may assume that the upkeep of a room is never cheaper than the upkeep of
any smaller room, that is, of any room which can hold a smaller number of
people.
The reservation system will be receiving multiple offers, each of
them specifying the amount of zlotys for rental of any room (
)
for one particular day and the minimal capacity of the requested room
(
).
For each offer, only a single room can be rented.
And conversely: each room can accommodate only a single offer.
Your friend has decided not to accept more than 
offers.
Knowing you are a skilled programmer, your friend asked you to implement the part of the system which finds the maximum profit (total income from renting out rooms minus their upkeep) he can make by accepting some of the offers.
Input
The first line of the standard input contains three integers 
, 
,
and 
(
, 
), denoting
the number of rooms in the hotel, the number of offers received
and the maximum number of offers your friend is willing to accept.
The next 
lines describe the rooms, with the 
-th of these lines
containing two integers 
, 
representing the upkeep of the room
in zlotys and the capacity of the room (
).
The next 
lines describe the offers, with the 
-th of these lines
containing two integers 
, 
representing the offered rental price
in zlotys and the minimal capacity of the requested room
(
).
You may assume that in test cases worth 40 points in total an additional
inequality 
holds.
Output
The first and only line of the standard output should contain one integer
equal to the maximum profit your friend can achieve accepting at most 
of
the offers.
Note that the profit might get big.
Example
For the input data:
3 2 2 150 2 400 3 100 2 200 1 700 3
the correct result is:
400
Explanation of the example: Your friend can accept both offers, renting out rooms number 2 and 3.
Task author: Jakub Pachocki.